Aminet 40/Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso/Aminet/dev/basic/DLL.lha/DLL/DLL.Readme

Text File | 2000-09-11 | 24.6 KB | 751 lines

        Dynamic Linked Lists with variable length items

                        by Tony Rolfe

                  [e-mail]

                         August 2000

                 Original code by Dave Newton


1. Introduction

   DLL.bb2 V3.0 By Tony Rolfe ([e-mail])

   Dynamic Linked Lists variable sized items for BLITZ BASIC 2

   These are a functional replacement for the List Arrays supplied with Blitz
   Basic 2.


   The fundamental difference between these routines and standard list arrays
   is that there is no need to define the maximum size of a list.  Standard
   Blitz Lists are defined with a command of the form

       DIM List Name.Type(MaxSize)

   With DLL the only limit on the number of entries is the amount of available
   memory.   Actually, the number of entries is held in a longword variable so
   the real limit is about 2,000,000,000. If anyone has problems with this
   limit please let me know.

   All the original commands are replicated here.   Command names have had an
   underscore added in the middle and the names fully capitalized.   Thus, the
   original AddItem() command has been replaced by ADD_ITEM{}.

   A number of additional functions have also been added.


   In this archive you should find:
      This Readme file (DLL.Readme)
      An AmigaGuide version of this information (dll.Guide)
      DLL main routines (dll.bb2 and dll.asc)
      DLL quicksort routines (dllsort.bb2 and dllsort.asc)
      DLL example program (dllexample.bb2 and dllexample.asc)
      Sample Fatal_Error routine (Fatal_Error.bb2 and Fatal_Error.asc)
      3 Options for String Compare Routines (Compare_Strings_X.bb2 and .asc)

   All the source code is provided as tokenised (.bb2) files and plain ASCII
   (.asc) files. This is so that if you have any tokenisation problems when
   loading the .bb2 files you can simply load the .asc files and then save
   them over the .bb2 files.


2. Distribution

   DLL is PD.  It is "Do-What-You-Like-Ware".

   Feel free to copy it and distribute it as you see fit.

   If, however, you make any significant changes, please forward a copy
   of the changes to me so I can maintain a central copy of DLL.

   Neither Dave Newton nor I can accept any responsibility for any harm to
   hardware or software caused directly or indirectly from the use of this
   source code and/or extracts of this source code compiled.

   But a credit for these routines in your software/manual would be nice :).


3. Getting Started

Before you start to use DLL you need to make one fundamental decision:

How do you want a DLL function to behave if it encounters an unrecoverable
error?   The original (Dave Newton) version of DLL had the function return
a True or False value to tell if it was successful.   My own preference is
for low level routines to handle their own errors and not bother returning
to the calling routine if they couldn't perform their function.

Immediately following the introductory comments in DLL.bb2, is the line

#DLL_TRAP_ERRORS = 1 ;

If you wish to maintain the original version of the code, set this flag to 0.
This will make you use code like:

If ADD_ITEM{*TheList}
   ; success
Else
   ; handle the error
Endif

If you wish to have each routine handle its own errors, set the flag to 1.
You will need to provide a function called Fatal_Error{}, which accepts a
string argument.   A sample is provided which simply displays the string
and ends the program.  The above code can now be replaced with:

ADD_ITEM{*TheList}

Having set the flag, save the file as a tokenized source.   Now you can
begin to use DLL.



For each program, you also need to decide how the sort routines should
handle string comparisons.   Three string compare routines are provided.
Include the required one before DLL.bb2

Compare_Strings_S.bb2   This is a case-sensitive routine ("CAT" <> "cat")
Compare_Strings_I.bb2   This is a case-insensitive routine ("CAT" = "cat")
Compare_Strings_IL.bb2  This is a case-insensitive routine which treats
                        strings as being equal if they have different
                        numbers of trailing spaces ("CAT   " = "cat")

XINCLUDE Compare_Strings_X.bb2



Now you need to include the dll routines somewhere near the top of your
program.   This must be after the appropriate Compare_Strings routine.
It does not matter whether or not the DLL routines are actually executed.

XINCLUDE "DLL.bb2"


Next you need to create a newtype for YOUR list item. You must include
a DLL node as your first variable in the newtype, otherwise you are free
to do anything a newtype will allow.


Newtype .myitem
  node.dll         ; Must be the first item
  namestring.s
  amount.w
  cost.l
End Newtype



Then you MUST do 3 steps before you can actually use the list.

1. Create a variable to hold a pointer to the current list item. You do
   this with Deftype and it MUST create a POINTER variable type.

   Deftype .myitem *MyItemPtr


2. Initialize the list.   This creates the List Header and also creates a
   dummy item.

   *MyList.dllhead = INIT_LIST{&*MyItemPtr,SizeOf .myitem}

   INIT_LIST is a function of the DLL includes. You must always pass the
   address of your current item pointer to this routine (&*MyItemPtr). To all
   other routines you must pass the head of the list as a pointer.

   You must also pass the size of your item, with Sizeof .myitem, as the
   second parameter to the INIT_LIST function.  This function returns the
   address of the head of the list (a dllhead type), which you save in a
   pointer, so you can reference the list later on.  If you are planning to
   have variable length items, you MUST set this length to at least sufficient
   to include all string variables in the longest item.   If there are no
   string items then a minimum of one numeric field must be included after
   the node.
                                                                           Ë


3. You MUST tell DLL about all the string variables in your newtype.
   This is because, when an item is killed in the list, DLL needs to know
   where the string variables (if any) are, so that it can deallocate them.
   Otherwise you would lose memory while the program is running.

   All you have to do is to set all your non string variables to -1 and
   your string variables to "", using the dummy item created in step 2.  If
   you have a fixed array [] in the item, you must set all array items to
   -1 or "" as well).  You MUST do this even if there are no strings in the
   NewType.

   In the above example, use the following code:

   *MyItemPtr\\namestring="",-1,-1
   SET_STRING_POSITIONS{*MyList}

Now your list is ready for use. Be aware that the current item doesn't
exist yet, you are simply pointing at the head of the list. So don't
access any of the item variables, until you have used one of the add item
routines.

If you want more than one DLL list in your program, repeat steps 1 - 3
above for each list.


4. All the Functions

4.1. ADD_FIRST

ret.b = ADD_FIRST{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 0)

ADD_FIRST{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 1)

Adds a new (blank) item as the first item in the list. If a function,
it will return true if it successfully added an item, otherwise it returns
false.

If an item was added, the current item pointer (your list pointer variable)
will point to the newly added item.

 Same as ADD_ITEM, except that it inserts the new item as the last item in
the list.

4.2. ADD_ITEM

ret.b = ADD_ITEM{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 0)

ADD_ITEM{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 1)

Adds a new (blank) item to the list, at the current position. If a function,
it will return true if it successfully added an item, otherwise it returns
false.

If an item was added, the current item pointer (your list pointer variable)
will point to the newly added item.

4.3. ADD_LAST

ret.b = ADD_LAST{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 0)

ADD_LAST{*listhead.dllhead,itemsize.l} (with #DLL_TRAP_ERRORS = 1)

Adds a new (blank) item as the last item in the list. If a function,
it will return true if it successfully added an item, otherwise it returns
false.

If an item was added, the current item pointer (your list pointer variable)
will point to the newly added item.

 Same as ADD_ITEM, except that it inserts the new item as the last item in
the list.

4.4. CLEAR_LIST

CLEAR_LIST{*listhead.dllhead}

 Kills all the items in the list, but keeps the list head information
 so that you can resuse the list (ie, ready for ADD_ITEM).

4.5. FIRST_ITEM

ret.l = FIRST_ITEM{*listhead.dllhead}

Sets the current item pointer for the list to the first item in the list if
available. Returns true if successful, otherwise returns false.

4.6. GET_CURRENT_ITEM

*ItemPointer.dll = GET_CURRENT_ITEM{*listhead.dllhead}

Returns the address of the current item.

Useful only when a common routine is being used to handle multiple lists.

4.7. GET_LIST_POS

position.l = GET_LIST_POS{*listhead.dllhead}

Returns the position of the current item in the list. The first item
is number 1.

Doesn't change the list's current item pointer.

4.8. GET_LIST_SIZE

Count.l = GET_LIST_SIZE{*listhead.dllhead}

Returns the number of items in the list.

Doesn't change the list's current item pointer.

4.9. ITEM_STACK_SIZE

ret.b = ITEM_STACK_SIZE{*listhead.dllhead,depth.l}  (with #DLL_TRAP_ERRORS = 0)

ITEM_STACK_SIZE{*listhead.dllhead,depth.l}  (with #DLL_TRAP_ERRORS = 1)

Sets the list stack size (for PUSH_ITEM, and POP_ITEM) to depth. Make
sure never to push more items than there is room for on the list stack.

Default is 8.

If there are any positions pushed onto the stack when this command is
executed, they will be discarded and the item stack will be reset at the
beginning of the new sized item stack.

Doesn't change the list's current item pointer.

See also PUSH_ITEM, POP_ITEM

4.10. INIT_LIST

*Listhead.dllhead = INIT_LIST{&*listitem.dll,itemsize.l}

Initilizes the list for the first time.  After calling this you need to
set the string positions...see SET_STRING_POSITIONS.  Returns the head of
the list if succesful otherwise returns 0.

Always call in the style of the following line:

*listhead.dllhead=INIT_LIST{&*blah_item,sizeof .blah_item_type}

because you need to save the return head of the list address to pass
to the other routines.

4.11. KILL_ITEM

KILL_ITEM{*listhead.dllhead}

Kills the item at the current list position.

The list's current item pointer will point at the previous item (if any) or
at the list header if the first item was killed.

4.12. LAST_ITEM

ret.b = LAST_ITEM{*listhead.dllhead}

Sets the current item pointer for the list to the last item in the list if
available.  Returns true if successful, otherwise returns false.

4.13. NEXT_ITEM

ret.b = NEXT_ITEM{*listhead.dllhead}

Sets the current item pointer for the list to the next item in the list if
available.  Returns true if successful, otherwise returns false.

This is always a function.

4.14. NO_MORE_ITEMS

NO_MORE_ITEMS{*listhead.dllhead}

Sets the list's current item pointer to the last item in the list,
if available, but doesn't care if the list is empty.

Used to terminate loops of the form

     RESET_LIST{*MyList}

     While NEXT_ITEM{*MyList}

       If *MyItem\Key = WantedValue

         ; Process the item

         NO_MORE_ITEMS{*MyList}

       Endif

     Wend

     ; The wanted item is no longer available


Effectively identical to LAST_ITEM, but doesn't need a dummy return code

4.15. POP_ITEM

POP_ITEM{*listhead.dllhead}

Pop's the list's current item pointer from the list's item stack. Make
sure there is an item on the list stack to 'pop'.

Because the list can have been sorted between the push and pop commands
the internal current item position pointer can have been corrupted.  This
command includes an embedded RESET_LIST_POS to recalculate this pointer.
This can be slow for large lists

See also ITEM_STACK_SIZE, PUSH_ITEM

4.16. PREV_ITEM

ret.b = PREV_ITEM{*listhead.dllhead}

Sets the current item pointer for the list to the previous item in the
list if available.  Returns true if successful, otherwise returns false.

4.17. PUSH_ITEM

PUSH_ITEM{*listhead.dllhead}

Pushes the list's current item pointer onto the list's item stack. Make
sure you don't push more items than the list stack can hold.

See also ITEM_STACK_SIZE, POP_ITEM.

4.18. RESET_LIST_POS

RESET_LIST_POS{*listhead.dllhead}

Calculates the list position for the current list item.
Should only be needed by POP_ITEM.

Does a brute-force "start at the beginning and compare headers until
the current one is found" search which can be slow for big arrays.

4.19. RESET_LIST

RESET_LIST{*listhead.dllhead}

Resets the list to the head item (makes the next NEXT_ITEM return the
first item in the list if available!).

4.20. SET_LIST_POS

ret.b = SET_LIST_POS{*listhead.dllhead,listpos.l} (with #DLL_TRAP_ERRORS = 0)

SET_LIST_POS{*listhead.dllhead,listpos.l} (with #DLL_TRAP_ERRORS = 1)

Sets the list's current item pointer to the item in the list
at the supplied listpos position.

This takes into account the current list position at the time the
command was issued and takes the shortest of the following five
options:

o  Start at the front and count forwards
o  Start at the current position and count backwards
o  Stay in the current position
o  Start at the current position and count forwards
o  Start at the end of the list and count backwards

4.21. SET_STRING_POSITIONS

SET_STRING_POSITIONS{*listhead.dllhead}

Records the positions of all blitz string pointers, by looking through the
data section of the item for non negative values (-1 only). Before calling
this you MUST set all the non string variables in your head item to -1,
and all the string variables to "", to allow this function to tell the
difference and record the positions of strings, so KILL_ITEM can properly
deallocate the memory taken up by them.

4.22. SORT_LIST_ASCENDING

SORT_LIST_ASCENDING{*listhead.dllhead,entrypath.l,vartype.l}

Sorts the list items into ascending order using an insert sort. Entrypath
should be the offset in bytes of the variable in the item to use for sort
the list (ie, use sizeof .myitem\\mysortvarname).  Vartype should be one of
the following constants to define the variable type pointed to by the
entrypath.

#VARTYPE_BTYE, #VARTYPE_WORD, #VARTYPE_LONG, #VARTYPE_QUICK, #VARTYPE_FLOAT

The sort routine will corrupt the internal list position indicator.   For
this reason the sort routine includes a RESET_LIST, which forces the list
position indicator to zero.

4.23. SORT_LIST_DESCENDING

SORT_LIST_DESCENDING{*listhead.dllhead,entrypath.l,vartype.l}

Sorts the list items into descending order using an insert sort. Entrypath
should be the offset in bytes of the variable in the item to use for sort
the list (ie, use sizeof .myitem\\mysortvarname).  Vartype should be one of
the following constants to define the variable type pointed to by the
entrypath.

#VARTYPE_BTYE, #VARTYPE_WORD, #VARTYPE_LONG, #VARTYPE_QUICK, #VARTYPE_FLOAT

The sort routine will corrupt the internal list position indicator.   For
this reason the sort routine includes a RESET_LIST, which forces the list
position indicator to zero.

4.23. STRING_SORT_ASCENDING

STRING_SORT_ASCENDING{*listhead.dllhead,entrypath.l}

Sorts the list items into ascending order using an insert sort. Entrypath
should be the offset in bytes of the variable in the item to use for sort
the list (ie, use sizeof .myitem\\mysortvarname).   This variable MUST be a
string variable

The sort routine will corrupt the internal list position indicator.   For
this reason the sort routine includes a RESET_LIST, which forces the list
position indicator to zero.

4.24. STRING_SORT_DESCENDING

STRING_SORT_DESCENDING{*listhead.dllhead,entrypath.l}

Sorts the list items into descending order using an insert sort. Entrypath
should be the offset in bytes of the variable in the item to use for sort
the list (ie, use sizeof .myitem\\mysortvarname).   This variable MUST be a
string variable

The sort routine will corrupt the internal list position indicator.   For
this reason the sort routine includes a RESET_LIST, which forces the list
position indicator to zero.

5. Advantages of DLL over standard lists

DLL has a number of advantages over the original Blitz Lists.

1. You do not need to define a maximum size for the list.

2. Since the lists are referenced  by pointers, you can easily define common
   routines to handle multiple lists.

3. New functions GET_LIST_POS, GET_LIST_SIZE and SET_LIST_POS  mean that you
   do not need to keep track of item counts or positions

4. There is an internal position indicator which greatly speeds up moving
   around the list with SET_LIST_POS.

6. Disadvantages of DLL

There are two disadvantages to using DLL rather than Blitz Lists

1. Since DLL is a set of functions, written in Blitz Basic and Blitz Lists
   are in a library written in Assembler, DLL is about 10% slower than
   Blitz Lists.

2. DLL is more complicated to initilize than Blitz Lists.

   If you are familiar with the use of pointers and NewTypes, there should
   be no real problems.

   If Pointers and NewTypes are foreign languages, simply follow the
   syntax given.   The most important points to remember are that your
   List Name and Item Name must begin with an *, (which defines a pointer)
   and the INIT_LIST command must have an & in front of the *ItemName
   to pass the address of the pointer.

   The rest is simply calling functions.

7. QuickSort Routines

These routines are extra sort routines which are much faster than the
2 included in DLL, provided a large number of items are being sorted.
For small lists (less than 3000 items) the standard sort routines
are quicker.

These routines are kept in a seperate include (DLLSORT.bb2) so people who
do not need to sort lists may use the list routines without these extra
routines taking up space. You need to include DLL.bb2 before including
DLLSORT.bb2.

These routines require extra memory (just 4*number of items in list as it
uses a seperate list to sort faster, so a 200 item list would require an
extra 800 bytes for the temporary list) and lots of stack space, so make
sure you have plenty of stack space free before calling them.


QUICK_SORT_LIST_ASCENDING{*listhead.dllhead,entrypath.l,vartype.l}
QUICK_SORT_LIST_DESCENDING{*listhead.dllhead,entrypath.l,vartype.l}

These routines perform a quick sort on the list.

See SORT_LIST_ASCENDING for more info on the parameters.

For a quick string sort, use the constant #VARTYPE_STRING

Both quick sort routines will corrupt the internal current item position
indicator so a RESET_LIST{} is included to force the pointer to a correct
value.

7.  Variable size items

You can have indvidual items of different sizes, but you can't access
variables outside of your smaller type.

You must not cut any variable off with your smaller size, it must be
big enough to hold at least the dllnode header and must always end on
a variable, not in the middle of one. (especially NOT string variables
as when the item is cleared it will attempt to free the string if you have
left the start of a string variable inside the item, whether you have
left the whole string variable in or not!!!).

When doing the INIT_LIST, the size specified MUST be big enough to include
all string variables.


8. How to handle multiple lists with a common routine

Assume that you have three lists and want to perform some common operations
on them.

With standard Blitz Lists, you must either replicate the common code for
each list or else set up a flag (or ListNumber) to show which list is
being processed and then do things like

Select ListNumber
   Case 1
     If NextItem(List1()) then ; do something
   Case 2
     If NextItem(List2()) then ; do something
   Case 3
     If NextItem(List3()) then ; do something
End Select

Then, if you want to add another list, you need to modify all the select
blocks.


With DLL, you simply need to define a dummy list as:

DefType.dllhead *TheList

and a dummy item

Deftype.Item *TheItem

Your Item NewType should contain a node.dll as the first variable, plus
any common variables needed by the common routine.

Then, if you are processing *List1, *List2 and *List3 you need to
execute the following code

*TheList = *List1
gosub common_routine

*TheList = *List2
gosub common_routine

*TheList = *List3
gosub common_routine


and the common routine can now perform all operations on *TheList.

However, if the operation changes the current item pointer, the common
routine won't know which item pointer has changed.  To get the pointer
address, the common routine should use the GET_CURRENT_ITEM{} function:

If NEXT_ITEM{*TheList}
   *TheItem = GET_CURRENT_ITEM{*TheList}
   Value = *TheItem\Value
endif

Adding another list requires no changes to the common routine


9. Using DLL lists with GTListviews"

To use a DLL list with a GTListview you MUST set up the type for
the items in your DLL list to look like this:

   NEWTYPE.dllgtlvitem
      node.dll       ; Always the first item in DLL lists
      pad.w          ; The node must be followed by a word variable
      text.s         ; Followed by the text to be displayed in the GTListview
      ; Anything else you want to add can be at the end of the item
   END NEWTYPE

If you do not set up the items like this you risk either not seeing
anything in the GTListview or perhaps your program will crash.

Obviously the command for creating a GTListview requires that the list
parameter is a regular Blitz list array. Since we will not be using that
list with the GTListview we can create a dummy list, with no special
newtype.

However, this list MUST NEVER have any items in it - if you do intend on
having items in the dummy list, you must make sure that it has a newtype
which you would normally use for Blitz list arrays being displayed in
GTListviews (same as the above newtype but without the "node.dll" field).

When working with DLL lists and GTListviews, you generally need to use
GTSetAttrs, since all the specific GTListview commands require list arrays
as parameters.

So, the full steps involved would look something like this:

   ; Newtype for allowing us to display items in a GTListview
   NEWTYPE.dllgtlvitem
      node.dll       ; Always the first item in DLL lists
      pad.w          ; The node must be followed by a word variable
      text.s         ; Followed by the text to be displayed in the GTListview
      ; Anything else you want to add can be at the end of the item
   END NEWTYPE

   ; Our variables for working with the DLL list
   DEFTYPE.dllhead     *listhead
   DEFTYPE.dllgtlvitem *myitem

   ; Initialise DLL list here
   ; Add items as required here

   ; Create dummy list array. This one will always remain empty
   ; so it does not matter about the type used.
   Dim List dummy.w(0)

   ; Create GTListview and then use the DLL list straight away
   GTListview gtlist,id,x,y,w,h,text$,flags,dummy()
   GTSetAttrs gtlist,id,#GTLV_Labels,*listhead

   ; Open window and attach gtlist to it
   ; We can also set the DLL list onto the GTListview after we have
   ; attached the gtlist to a window using the same GTSetAttrs line
   ; as above. The GTListview will automatically be redrawn if it
   ; is in a gtlist that is attached to a window
   GTSetAttrs gtlist,id,#GTLV_Labels,*listhead

   ; If we want to modify the DLL list, we must do the same as we
   ; would normally have to do with GTListviews - detach the list
   ; from the GTListview, modify the list, then re-attach the list

   ; Detach DLL list from GTListview
   GTChangeList gtlist,id

   ; Modify DLL list in here

   ; Re-attach DLL list to GTListview
   GTSetAttrs gtlist,id,#GTLV_Labels,*listhead

Apart from the different method used to attach the DLL list to the
GTListview, and the slightly different newtype that is required, everything
else is the same as when you are using Blitz list arrays. See the example
program, dllexample.bb2, this shows you how to add a DLL list to a
GTListview.

10. Bugs  :(

   As far as I am aware, there are no bugs.   Anything that looks like a bug
   is actually the way it is supposed to work :-)

   If you don't like the way it's supposed to work, please send an email to
   [e-mail] with a subject line of DLL BUGS

   Don't simply say "It doesn't work"  because I will simply say "Yes it does".
   Make sure you have tried your code with the latest version of these routines.

   Please provide specific details of what you wanted it to do, what it did,
   whether it does it every time and the simplest version of your source
   code which contains the problem.

   If I can compile it, I can diagnose it (Note:  Not Fix it!)

11. Thanks

   I'd like to take a moment to thank:

   Dave Newton   for the original code.

   John Mason    for suggestions and ideas on strings!

   David McMinn  for ideas on attaching DLL Lists to GTListviews

   And, in general, everybody on the Blitz-list